//
//  20. 有效的括号.swift
//  手撕代码
//
//  Created by xiaoZuDeMeng on 2024/2/22.
//

import Foundation

//https://leetcode.cn/problems/valid-parentheses/
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//有效字符串需满足：
//
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
//
//
//示例 1：
//
//输入：s = "()"
//输出：true
//示例 2：
//
//输入：s = "()[]{}"
//输出：true
//示例 3：
//
//输入：s = "(]"
//输出：false
//
//
//提示：
//
//1 <= s.length <= 104
//s 仅由括号 '()[]{}' 组成

func 有效的括号(_ s: String) -> Bool {
    let map: [Character: Character] = [")": "(", "]": "[", "}": "{"]
    var lefts = [Character]()
    for char in s {
        if map.values.contains(char) {
            lefts.append(char)
        } else {
            guard !lefts.isEmpty, map[char] == lefts.removeLast() else {
                return false
            }
        }
    }
    return lefts.isEmpty
}

func 有效的括号1(_ s: String) -> Bool {
    var stack = [Character]()
    let chars = Array(s)
    let count = chars.count
    if count % 2 != 0 { return false }
    for c in chars {
        if c == "(" {
            stack.append(")")
        } else if c == "[" {
            stack.append("]")
        } else if c == "{" {
            stack.append("}")
        } else if stack.isEmpty || stack.last != c {
            return false
        } else {
            stack.removeLast()
        }
    }
    return stack.isEmpty
}
